User authentication is an important requirement for many systems. For example, a software application may host different respective accounts for different users and require a user to authenticate his identity as a condition of granting the user access to his account. Internet applications, for example, are often shared by millions of different users and typically require each user to authenticate his identity (e.g., by providing authenticating credentials) as a precondition of gaining access to the user's account. Although authentication is often used to verify a user's specific identity, the process may be more generally thought of as verification that a user possesses a certain set of one or more privileges.
Many authentication procedures rely on a user's ability to reproduce a password. For example, many network services (e.g., web applications) authenticate users with a login procedure that requires the user to reproduce a username and password combination. Access to corporate facilities and other facilities and services may require the user to reproduce a password and personal identification number (PIN) combination and/or proof of possession of some physical token (e.g., public/private key, access/payment smart card, certificate, etc.). Many other variations exist.
Password-based authentication schemes are susceptible to attackers who are able to guess a user's password. For example, if the user has chosen a “weak” password (e.g., one with few characters), a brute force attacker may discover the password by repeatedly guessing passwords and attempting to authenticate.
To thwart attackers, it may be desirable that users select “strong” passwords that are difficult to guess. A password may be strong because it is composed of many characters and/or many types of characters chosen from a large character set. Such passwords may be referred to as “high-entropy.” Weaker, “low-entropy” passwords may include fewer characters and/or fewer types of characters that may be chosen from a smaller character set.
To ensure high-entropy passwords, some systems impose password requirements (i.e., password policies) that prevent users from creating passwords that are too weak. Such requirements may include a minimum number of characters, maximum number of repeated characters, characters from several sets, no dictionary words, and other such requirements. Such minimum requirements for the complexity of a password may be referred to herein without distinction as password requirements or password policy.
Although high-entropy passwords may be desirable from a security perspective, such passwords are difficult to remember. As a result, users may select low-entropy passwords or select the same high-entropy password for multiple systems. Additionally, users may record their passwords, such as on paper or in a computer file. Unfortunately, all of these approaches compromise system security by making it easier for attackers to guess or steal a user's password.